import collections
class Solution(object):
    def catMouseGame(self, graph):
        n = len(graph)
        du = collections.defaultdict(int)
        c = collections.defaultdict(int)
        st = set()
        for i in range(1, n):
            for j in range(n):
                for u in graph[i]:
                    if u != 0:
                        du[(i, j, 1)] += 1
                for u in graph[j]:
                    du[(i, j, 2)] += 1
                if i == j:
                    c[(i, j, 2)] = 2
                    c[(i, j, 1)] = 2
                    st.add((i, j, 2))
                    st.add((i, j, 1))
                if j == 0:
                    c[(i, j, 2)] = 1
                    st.add((i, j, 2))
        while st:
            next_st = set()
            for x, y, name in st:
                state = c[(x, y, name)]
                last_name = 3 - name
                if last_name != state:
                    if last_name == 1:
                        for u in graph[y]:
                            du[(x, u, last_name)] -= 1
                            if du[(x, u, last_name)] == 0 and c[(x, u, last_name)] == 0:
                                next_st.add((x, u, last_name))
                                c[(x, u, last_name)] = 3 - last_name
                    else:
                        for u in graph[x]:
                            if u != 0:
                                du[(u, y, last_name)] -= 1
                                if du[(u, y, last_name)] == 0 and c[(u, y, last_name)] == 0:
                                    next_st.add((u, y, last_name))
                                    c[(u, y, last_name)] = 3 - last_name
                else:
                    if last_name == 1:
                        for u in graph[y]:
                            if c[(x, u, last_name)] == 0:
                                next_st.add((x, u, last_name))
                                c[(x, u, last_name)] = 1
                    else:
                        for u in graph[x]:
                            if u != 0:
                                if c[(u, y, last_name)] == 0:
                                    next_st.add((u, y, last_name))
                                    c[(u, y, last_name)] = 2

            st = next_st
        return c[(2, 1, 1)]

                    








                    
                    
            

data = Solution()
graph = [[2,5],[3],[0,4,5],[1,4,5],[2,3],[0,2,3]]
print(data.catMouseGame(graph))
graph = [[1,3],[0],[3],[0,2]]
print(data.catMouseGame(graph))
graph = [[2,3],[2],[0,1],[0,4],[3]]
print(data.catMouseGame(graph))
graph = [[2,3,4],[2,4],[0,1,4],[0,4],[0,1,2,3]]
print(data.catMouseGame(graph))